package cn.edu.jxau.test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 付大石
 */

public class Main {

    public static void main(String[] args) {

        Student[] arr = new Student[] { new Student("aa", 10), new Student("bb", 10), new Student("cc", 20) };
        Student[] result = new Student[] { new Student("cc", 20), new Student("bb", 10), new Student("aa", 10) }; //false
//        Student[] result = new Student[] { new Student("cc", 20), new Student("aa", 10), new Student("bb", 10) }; //true
//        Student[] result = new Student[] { new Student("aa", 10), new Student("bb", 10), new Student("cc", 20) }; //throw exception
        System.out.println(check(arr, result));
    }

    /**
     * 检测排序结果是否稳定，数组元素必须实现有
     * 意义的{@code equals()}方法。
     * 
     * @param arr
     * @param result
     */
    private static <T extends Comparable<T>> boolean check(T[] arr, T[] result) {

        // 判断result是否有序（从小到大） //
        for (int i = 1; i < result.length; i++) {
            if (result[i].compareTo(result[i - 1]) < 0) {
                throw new RuntimeException("result不是有序的");
            }
        }

        // 检测排序算法结果是否稳定 //
        T[] arrCopy = (T[]) new Comparable[arr.length];
        System.arraycopy(arr, 0, arrCopy, 0, arr.length);
        sort(arrCopy); // 使用稳定算法排序
        System.out.println("*** " + Arrays.toString(arrCopy));
        for (int i = 0; i < arrCopy.length - 1; i++) {
            while (i < arrCopy.length - 1 && arrCopy[i].compareTo(arrCopy[i + 1]) == 0) {
                if (!arrCopy[i].equals(result[i])) {
                    return false;
                }
                i++;
            }
        }
        return true;
    }

    /**
     * 使用稳定的归并排序
     * 
     * @param arr
     * @param id
     */
    private static <T extends Comparable<T>> void sort(T[] arr) {

        T[] aux = (T[]) new Comparable[arr.length];
        sort(arr, aux, 0, arr.length - 1);
    }

    private static <T extends Comparable<T>> void sort(T[] arr, T[] aux, int low, int high) {

        if (high <= low) {
            return;
        }
        int mid = low + ((high - low) >> 1);
        sort(arr, aux, low, mid);
        sort(arr, aux, mid + 1, high);
        merge(arr, aux, low, mid, high);
    }

    private static <T extends Comparable<T>> void merge(T[] arr, T[] aux, int low, int mid, int high) {

        int i = low;
        int j = mid + 1;
        for (int k = low; k <= high; k++) {
            aux[k] = arr[k];
        }

        int k = low;
        while (i <= mid && j <= high) {
            if (aux[i].compareTo(aux[j]) <= 0) {
                arr[k++] = aux[i++];
            } else if (aux[i].compareTo(aux[j]) > 0) {
                arr[k++] = aux[j++];
            }
        }
        while (i <= mid) {
            arr[k++] = aux[i++];
        }
        while (j <= high) {
            arr[k++] = aux[j++];
        }
    }
}

class Student implements Comparable<Student> {
    private String name;
    private int source;

    public Student(String name, int source) {
        this.name = name;
        this.source = source;
    }

    @Override
    public boolean equals(Object s) {

        if (this == s) {
            return true;
        }
        if (s instanceof Student) {
            if (((Student) s).name.equals(name) && ((Student) s).source == source) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int compareTo(Student s) {
        return s.source - source;
    }

    @Override
    public String toString() {
        return "Student [name=" + name + ", source=" + source + "]";
    }
}